package gold.digger;

import gold.vo.ListNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC143 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public void reorderList(ListNode head) {
            if (null == head) return;

            Map<Integer, ListNode> map = new HashMap<>();
            int id = 0;
            ListNode cur = head;
            while (cur != null) {
                map.put(id++, cur);
                cur = cur.next;
            }

            cur = map.get(0);
            int i = 0, j = id - 1;
            while (true) {
                cur.next = map.get(j);
                cur = cur.next;

                ++i;
                --j;

                if (i >= j) {
                    if (i == j) {
                        cur.next = map.get(i);
                        cur = cur.next;
                    }
                    cur.next = null;
                    break;
                }

                cur.next = map.get(i);
                cur = cur.next;
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
        ListNode head = ListNode.createList("1->2->3->4->5");
        solution.reorderList(head);
    }

    public static void main(String[] args) throws Exception {
        LC143 an = new LC143();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
